Sau quá trình tu học dài hạn, ngày 27 tháng 3 năm 1937, chủng sinh Nguyễn Văn Bình được truyền chức linh mục tại Vương cung thánh đường Thánh Gioan Latêranô, Roma, Ý.[16] Sau khi trở thành linh mục, Nguyễn Văn Bình hỗ trợ mục vụ tại một số giáo xứ thuộc khu vực Roma. Tháng 8 năm 1938, theo yêu cầu từ giám mục Địa phận và không thể tiếp tục việc học,[18] ông trở về Việt Nam trong tình trạng sức khỏe suy kiệt. Tàu về đến Sài Gòn, linh mục Bình cần hai người trợ giúp mới có thể lên bờ. Sức khỏe Nguyễn Văn Bình trở nên tồi tệ kể từ khi ông mắc lao phổi rất nặng và bị xẹp phổi một bên. Kể từ thời điểm này đến khi qua đời, ông chỉ thở bằng một lá phổi, vai trở nên nghiêng một bên, mất cân đối. Về đến quê hương, linh mục Bình được bổ nhiệm coi sóc họ đạo Ðức Hòa (nay thuộc giáo phận Mỹ Tho), họ đạo vốn chỉ có 50 giáo dân, để hàng tuần có thời gian đến bệnh viện Chợ Rẫy chữa bệnh.[19] Tuy vậy, linh mục Bình bất chấp các khó khăn với mục đích giữ việc sinh hoạt tôn giáo tại họ đạo này vì cho rằng mình cần tập làm quen với khó khăn.[20]

Năm 1942, linh mục Nguyễn Văn Bình trở lại Sài Gòn vì được bổ nhiệm làm giáo sư Tiểu Chủng viện Sài Gòn,[21] từ năm 1947 lại kiêm thêm linh hướng trường Taberd trong một năm.[14] Vì có xu hướng thể hiện quan điểm quốc gia và dân tộc, ngoài linh mục Bình còn có linh mục Phaolô Nguyễn Văn Đậu bị điều chuyển khỏi chủng viện cùng một ngày. Cả hai linh mục này đều bị chuyển đi các giáo xứ ít người ở vùng cao nguyên.[22]

Theo báo Sài Gòn Giải phóng, đầu năm 1947, Pháp khởi sự cuộc chiến tranh tái xâm lược Việt Nam. Lệnh kháng chiến từ phía chính quyền Việt Nam Dân chủ Cộng hòa cũng đã được ban hành. Có bốn linh mục ở miền Nam là các linh mục Hiền, Kính, Luật và Sang đã đi chiến khu tham gia kháng chiến và dư luận cho rằng các linh mục này “lạc đàng”. Một tờ truyền đơn được phổ biến vào thời điểm đó cho rằng các linh mục này là những người yêu nước. Giám mục Jean Cassaigne Sanh yêu cầu linh mục Nguyễn Văn Bình bày tỏ ý kiến về nội dung của tờ truyền đơn. Câu trả lời của linh mục Bình không làm hài lòng giám mục Sanh. Sau lần hỏi đáp với vị Đại diện Tông Tòa Sài Gòn, Nguyễn Văn Bình được điều chuyển rời khỏi chủng viện.[23] Ngoài ra, cũng vì cùng bị nghi ngờ là chủ xướng việc phân phát truyền đơn trên, ngoài linh mục Nguyễn Văn Bình còn có ba linh mục khác, trong đó có linh mục Giuse Phạm Văn Thiên bị điều chuyển khỏi các chức vụ tại Chủng viện.[24]

Từ năm 1948, Nguyễn Văn Bình làm linh mục quản nhiệm họ đạo Cầu Đất, một họ đạo heo hút tại Đà Lạt, nơi có khoảng 300 giáo dân, tuy vậy trải trên địa bàn rộng gồm Đơn Dương, M’lọn, Bắc Hội và Đa Thọ.[4][19][23] Khi nhận được tin bổ nhiệm, linh mục Nguyễn Văn Bình nhận nhiệm sở mới. Tại đó ngoài công việc mục vụ, ông còn thực hiện tờ báo mang tên "Tông Đồ" từ năm 1948 đến năm tháng 7 năm 1950 thì chuyển giao cho linh mục Lê Văn Nhơn.[14][18][23] Trong thời kỳ quản nhiệm tại đây, linh mục Nguyễn Văn Bình sống đời thanh bần, có lúc ông đi bộ hơn 10 km để đến thăm giáo dân. Trong khoảng thời gian này, ông cũng hoàn thành các công việc mục vụ như xây dựng nhà thờ Đơn Dương, dựng lầu chuông nhà thờ Cầu Đất, xây Nhà nguyện ở cây số 12 (nay là nhà thờ Đa Lộc, giáo phận Đà Lạt) và cử hành bí tích Rửa Tội cho hàng trăm người mới nhập đạo Công giáo. Ngoài các công tác mục vụ, Nguyễn Văn Bình còn quan tâm đến đời sống khó khăn về vật chất của giáo dân. Những chiều Tất Niên, ông đi bộ 6 km trên quãng đường có nhiều cọp và bò rừng nhằm mục đích mua củi, gạo phát cho người nghèo sử dụng trong dịp Tết, đặt bánh cho thiếu nhi mừng giao thừa.[19]

Linh mục Nguyễn Văn Bình được thuyên chuyển về Sài Gòn làm giáo sư Đại Chủng viện Sài Gòn vào tháng 3 năm 1955.[14][18]